{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import numpy as np\n",
    "import time\n",
    "import matplotlib.pyplot as plt\n",
    "Alpha=0.1 #学习速率\n",
    "Beta=0.9 #对未来奖励的衰减度\n",
    "Epsilon_start=1#选择随机动作的概率 Epsilon\n",
    "Epsilon_stop=0.01\n",
    "decay_rate=0.00001\n",
    "N_Mesh=10\n",
    "N_States=100#假设网格为5*5\n",
    "Actions=['left_Three','left_Four','left_six','up_Three','up_Four','down']\n",
    "Obstable=[3,5,16,21,23,27,29,31,33,34,56,57,66,67,78,81,86,98]\n",
    "#——————————————————————————————————————————————————————————————————————————————————————————————————————————————————————\n",
    "def Caculate_coordinate(State):\n",
    "    X_Axis=0.5+(State-1)%N_Mesh\n",
    "    Y_Axis=0.5+((State-1)//N_Mesh)\n",
    "    return X_Axis,Y_Axis\n",
    "def Initial_Q_Table (N_States,Actions):#以状态数和动作为变量，返回Q表\n",
    "    Q_Table=np.zeros([N_States,len(Actions)])#初始化Q_表\n",
    "    Q_Table=pd.DataFrame(Q_Table,index=np.arange(1,N_States+1),columns=Actions)#Q_表定义行列标签\n",
    "    print ('初始化Q表完成') \n",
    "    return Q_Table\n",
    "#——————————————————————————————————————————————————————————————————————————————————————————————————————————————————————\n",
    "def Select_Action(State,Q_Table,ep):#根据目前的状态选择动作,返回执行动作\n",
    "    Epsilon=Epsilon_stop+(Epsilon_start-Epsilon_stop)*np.exp(-decay_rate*ep)\n",
    "    States_Actions=Q_Table.loc[[State],:]#选择目前状态下，取出Q表的目前的状态行,state选择为数字\n",
    "    if(np.random.rand()<Epsilon or np.all(States_Actions==[0])):#其实np.all(States_Action==[0])也行\n",
    "        Execute_Action=np.random.choice(Actions)\n",
    "    else:\n",
    "        #Q_T=Q_Table.T\n",
    "        #G=(Q_Table.T).loc[:,[State]]\n",
    "        Execute_Action=np.array(pd.DataFrame.idxmax((Q_Table.T).loc[:,[State]]))[0]#这里真心累，有毒\n",
    "    return Execute_Action\n",
    "#———————————————————————————————————————————————————————————————————————————————————————————————————————————\n",
    "def Next_State(State,Execute_Action):#根据目前状态个选择的动作,返回即时奖励和新状态\n",
    "    if(Execute_Action=='left'):\n",
    "        #目标在右上角，如果Execute_Action为‘left’，不可能到达目标\n",
    "        if(State%N_Mesh==1):#判断是不是在网格最左边\n",
    "            State=State\n",
    "            R=-10000\n",
    "        elif((State+1) in Obstable):\n",
    "            State=State-1\n",
    "            R=-10000\n",
    "        else:\n",
    "            State=State-1\n",
    "            R=0\n",
    "    elif(Execute_Action=='right'):\n",
    "        if(State==N_States-1):\n",
    "            State='End'\n",
    "            R=10\n",
    "        elif(State%N_Mesh==0):\n",
    "            State=State\n",
    "            R=-10000\n",
    "        elif((State+1) in Obstable):\n",
    "            State=State+1\n",
    "            R=-10000\n",
    "        else:\n",
    "            State=State+1\n",
    "            R=0.002\n",
    "    elif(Execute_Action=='up'):\n",
    "        if(State==N_States-N_Mesh):\n",
    "            State='End'\n",
    "            R=10\n",
    "        elif(N_States+1-N_Mesh<=State<=N_States-1):\n",
    "            State=State\n",
    "            R=-10000\n",
    "        elif((State+10) in Obstable):\n",
    "            State=State+10\n",
    "            R=-10000\n",
    "        else:\n",
    "            State=State+N_Mesh\n",
    "            R=0.002\n",
    "    else:\n",
    "        if(0<=State<=N_Mesh):\n",
    "            State=State\n",
    "            R=-10000\n",
    "        elif((State-10) in Obstable):\n",
    "            State=State-10\n",
    "            R=-10000\n",
    "        else:\n",
    "            R=0\n",
    "            State=State-10\n",
    "    return State,R\n",
    "        \n",
    "#————————————————————————————————————————————————————————————————————————————————————————————\n",
    "def Run_Function():\n",
    "    #——————————————————————————————————————————————————画图程序部分\n",
    "    \n",
    "    \n",
    "    #——————————————————————————————————————————————————\n",
    "    Q_Table=Initial_Q_Table (N_States,Actions)\n",
    "    Step=0 \n",
    "    for episode in np.arange(300) :#跑20回合\n",
    "        if(episode%300==0):\n",
    "            print('Q_Table,%d'%episode)\n",
    "            Q_Table\n",
    "#         fig=plt.figure()\n",
    "#         ax=fig.gca()\n",
    "#         ax.set(xlim=[0, N_Mesh], ylim=[0, N_Mesh])\n",
    "#         ax.set_xticks(np.arange(0,(N_Mesh+1)))\n",
    "#         ax.set_yticks(np.arange(0,(N_Mesh+1)))\n",
    "#         plt.grid()\n",
    "        print('episode is %d' % episode)\n",
    "        if(np.random.rand()<0.4):\n",
    "            State_=1 #定义起点 \n",
    "            print(\"Normal_start:%d\"%State_)\n",
    "        else:\n",
    "            State_=np.random.randint(low=5, high=100)\n",
    "            print(\"Random_start:%d\"%State_)\n",
    "        Is_End=False\n",
    "        while not Is_End:\n",
    "            A=Select_Action(State_,Q_Table,Step)\n",
    "            Next_S,R=Next_State(State_,A)\n",
    "            #print(Next_S)\n",
    "            Q_Table_S_A=Q_Table.loc[[State_],[A]]\n",
    "            if Next_S!='End':\n",
    "                D_T=np.array((Q_Table.loc[[Next_S],:]).T)\n",
    "                Q_Target=R+Beta*D_T.max() #Next_S状态中的可选动作中的最大Q值动作\n",
    "                Step+=1\n",
    "            else:\n",
    "                Q_Target=R\n",
    "                Step+=1\n",
    "                Is_End=True #目的是结束循\n",
    "#————————————————————————————————————————————————————————————————————————————画图程序\n",
    "#             X_State,Y_State=Caculate_coordinate(State_)\n",
    "#             if(Next_S)=='End':\n",
    "#                 H=N_States\n",
    "#             else:\n",
    "#                 H=Next_S\n",
    "#             X_Next_State,Y_Next_State=Caculate_coordinate(H)                      \n",
    "#             if(Step==0):\n",
    "#                 plt.scatter(X_State,Y_State)  \n",
    "#             else:\n",
    "#                 plt.scatter(X_State,Y_State) \n",
    "#                 plt.scatter(X_Next_State,Y_Next_State)\n",
    "#                 plt.plot([X_State,X_Next_State],[Y_State,Y_Next_State])\n",
    "#————————————————————————————————————————————————————————————————————————————\n",
    "            Q_Table.loc[[State_],[A]]+=Alpha*(Q_Target-Q_Table_S_A)\n",
    "            State_=Next_S\n",
    "        print(Step)\n",
    "        print(Epsilon_stop+(Epsilon_start-Epsilon_stop)*np.exp(-decay_rate*Step))\n",
    "        #plt.show()\n",
    "        #print(Q_Table)\n",
    "    return Q_Table\n",
    "#————————————————————————————————————————————————————————————————————————————————————————————————————\n",
    "Q__Table=Run_Function()\n",
    "Q__Table\n",
    "Final_Q_Table=np.array(Q__Table)\n",
    "#—————————————————————————————————————————————————————————————————————————————————————————————————————\n",
    "def Plot_Final_Graph(Q_TABLE):\n",
    "    fig=plt.figure()\n",
    "    ax=fig.gca()\n",
    "    ax.set(xlim=[0, N_Mesh], ylim=[0, N_Mesh])\n",
    "    ax.set_xticks(np.arange(0,(N_Mesh+1)))\n",
    "    ax.set_yticks(np.arange(0,(N_Mesh+1)))\n",
    "    plt.grid()\n",
    "    State_Start=1\n",
    "    State=State_Start\n",
    "    Step=1\n",
    "    while(State!=N_States):\n",
    "        Action=np.argmax((Q_TABLE[State-1]))\n",
    "        if(Action==0):\n",
    "             Next_State=State-1\n",
    "        elif(Action==1):\n",
    "             Next_State=State+1\n",
    "        elif(Action==2):\n",
    "             Next_State=State+N_Mesh\n",
    "        else:\n",
    "             Next_State=State-N_Mesh\n",
    "        Step+=1\n",
    "        print(Next_State)\n",
    "        X_State,Y_State=Caculate_coordinate(State)\n",
    "        X_Next_State,Y_Next_State=Caculate_coordinate(Next_State)\n",
    "        if(Step==0):\n",
    "            plt.scatter(X_State,Y_State)  \n",
    "        else:\n",
    "            plt.scatter(X_State,Y_State) \n",
    "            plt.scatter(X_Next_State,Y_Next_State)\n",
    "            plt.plot([X_State,X_Next_State],[Y_State,Y_Next_State])\n",
    "        for J in np.arange(len(Obstable)):\n",
    "            plt.scatter((Caculate_coordinate(Obstable[J]))[0],(Caculate_coordinate(Obstable[J]))[1],marker=\"x\")\n",
    "        print(X_State,Y_State)\n",
    "        print(X_Next_State,Y_Next_State)\n",
    "        State=Next_State\n",
    "    plt.show()\n",
    "#——————————————————————————————————————————————————————————————————————————————————————————————————————————\n",
    "Plot_Final_Graph(Final_Q_Table)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
